#include <vector>
#include <stack>

/**
 * Pool class
 * A container with a persistent indexing scheme
 * Indexes into contained objects don't get invalidated after deletes
 * 
 * Size is always maximum size of contained objects as of yet
 */

template <typename T>
class Pool
{
private:
	std::vector<T> data_;
	std::stack<int> free_;
	std::vector<bool> occupied_;
	
public:
	T& operator[](int i)
	{
		return data_[i];
	}
	
	T const & operator[](int i) const
	{
		return data_[i];
	}
	
	/*
	 * Adds items into a free slot if available, extends the pool otherwise
	 */
	
	int insert( T const & value )
	{
		if( free_.size() > 0 )
		{
			int index = free_.top();
			free_.pop();
			data_[index] = value;
			occupied_[index] = true;
			return index;
		}
		else
		{
			data_.push_back( value );
			occupied_.push_back( true );
			return data_.size()-1;
		};
	}
	
	/*
	 * Invalidates object at selected index
	 * Index will be used for latter additions
	 */
	void remove( int i )
	{
		free_.push( i );
		occupied_[i] = false;
	}
	
	/*
	 * Returns amount of stored objects
	 */
	int size()
	{
		return data_.size() - free_.size();
	}
	
	/*
	 * Returns capacity of pool
	 */
	int capacity()
	{
		return data_.size();
	}
	
	/*
	 * Returns whether selected element is occupied
	 */
	bool occupied( int i )
	{
		return occupied_[i];
	}
	
}; // class Pool
